class Solution {
public:
    int dp[999999];
    int climbStairs(int n) {
        fill(dp,dp+999999,-1);
        dp[1]=1;dp[2]=2;
        return digui(n);
    }
    int digui(int n){
        if(dp[n]!=-1){return dp[n];}
        dp[n]=digui(n-1)+digui(n-2);
        return dp[n];
    }
};